home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2000 / MacHack 2000.toast / pc / The Hacks / Softshoe / Lisa's Portable Parts / BinarySearch / BinarySearch.h < prev   
Encoding:
Text File  |  2000-06-23  |  1.2 KB  |  61 lines
  1. // BinarySearch.h
  2.  
  3. #ifndef BinarySearch_h
  4. #define BinarySearch_h
  5.  
  6. #ifndef Integers_h
  7. #include "Integers.h"
  8. #endif
  9.  
  10. /***
  11.     The intent here is that
  12.     
  13.         BinarySearch<T> search( start, gap );
  14.         while ( search.Unfinished() )
  15.             search.Narrow( Condition( search.Position() ) );
  16.     
  17.     leaves search.Position() pointing to the first
  18.     place in start..start+gap where Condition is true,
  19.     or start+gap if Condition is never true.
  20.     
  21.     For this to work, Condition must be monotonic from false
  22.     to true as the position increases.
  23.     
  24. ***/
  25.  
  26. template < class IndexType >
  27. class BinarySearch
  28.   {
  29.     private:
  30.         IndexType low;
  31.         IndexType middle;
  32.         uint32 gap;
  33.     
  34.     public:
  35.         BinarySearch( IndexType start, uint32 theGap )
  36.           : low( start ),
  37.              gap( theGap ),
  38.              middle( low + theGap / 2 )
  39.           {}
  40.         
  41.         bool Finished() const                    { return gap == 0; }
  42.         bool Unfinished() const                    { return gap > 0; }
  43.         
  44.         const IndexType& operator*() const    { return middle; }
  45.         
  46.         void Narrow( bool downward )
  47.           {
  48.             if ( downward )
  49.                 gap = gap / 2;                // gap = middle - low;
  50.              else
  51.               {
  52.                 gap -= (gap / 2) + 1;    // gap -= middle - low + 1;
  53.                 low = middle + 1;
  54.               }
  55.             
  56.             middle = low + gap/2;
  57.           }
  58.   };
  59.  
  60. #endif
  61.